package NewCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangchenghao
 * @date 2021/7/22
 **/
public class NC73 {
    public int MoreThanHalfNum_Solution(int[] array) {
        Map<Integer, Integer> counts = countNums(array);
        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }
        return majorityEntry.getKey();
    }

    public Map<Integer, Integer> countNums(int arr[]) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        return map;
    }
}
